package leecode

func wordPuzzle(grid [][]byte, target string) bool {
	path := make([][]bool, len(grid))
	for i := 0; i < len(path); i++ {
		path[i] = make([]bool, len(grid[i]))
	}
	for i := 0; i < len(grid); i++ {
		for j := 0; j < len(grid[i]); j++ {
			if backtracking(grid, target, path, 0, i, j) {
				return true
			}
		}
	}
	return false
}

// 回溯查找一条符合的路径
func backtracking(grid [][]byte, target string, path [][]bool, pathLength, row, column int) bool {
	//长度为单词长度时结束调用
	if pathLength == len(target) {
		return true
	}
	//检测是否越界
	if row < 0 || row >= len(grid) || column < 0 || column >= len(grid[0]) {
		return false
	}
	//是否符合条件  path[row][column] 路径是否被访问过
	if path[row][column] || grid[row][column] != target[pathLength] {
		return false
	}
	path[row][column] = true
	res := backtracking(grid, target, path, pathLength+1, row-1, column) ||
		backtracking(grid, target, path, pathLength+1, row+1, column) ||
		backtracking(grid, target, path, pathLength+1, row, column-1) || backtracking(grid, target, path, pathLength+1, row, column+1)
	path[row][column] = false
	return res
}
